#!/usr/bin/python

""" Since the list is not hashable in the graph search, I change to tuple"""

from utils import *;
from search import *;

class EightPuzzle(Problem):
	"""The problem of solving a eight puzzle problem """
	def __init__(self, state):
		self.initial = tuple(state)
				
	def successor(self, state):
		"""In the 8 puzzle problem, move the blank to other position."""
		result = []
		position = list(state).index(0)	
		for action, newposition in self.possible_position(position).iteritems():
			new = list(state[:])
			new[newposition], new[position] = new[position], new[newposition]
			result.append((action, tuple(new)))
		return result
		
	def possible_position(self, position):
		"""return the possible position"""
		result = {};
		col = position % 3;
		row = position // 3;
		# add the action in a circle manner. No dead iter now
		if row != 2:
			result['D'] = position +3
		if col != 0: 
			result['L'] = position -1	
		if row != 0:
			result['U'] = position -3
		if col != 2:
			result['R'] = position +1

		return result

	def goal_test(self, state):
		if state[0] != 0:
			return False
		elif state[1] !=1:
			return False
		elif state[2] !=2:
			return False
		elif state[3] !=3:
			return False
		elif state[4] !=4:
			return False
		elif state[5] !=5:
			return False
		elif state[6] !=6:
			return False
		elif state[7] !=7:
			return False
		elif state[8] !=8:
			return False
		else:
			print state
			return True 	
			# print state
	
	def h(self, node):
		"""Heuristic function"""
		# print node.state
		temp=list(node.state)
		sum=0
		for x in range(8):	# mahatten distance
			sum = sum + abs(temp.index(x)-x)
		return sum
		
	def getvalues(self, key):
		values = [1, -1, self.nsize, -self.nsize]
		valid = []
		for x in values:
			if key + x in range(0, self.tsize):
				if x == 1 and key in range(self.nsize - 1, self.tsize, 
					self.nsize):
					continue
				if x == -1 and key in range(0, self.tsize, self.nsize):
					continue
				valid.append(x)
		return valid

	def expand(self, st):
		"""Provide the list of next possible states from current state."""
		
		pexpands = {}
		for key in range(self.tsize):
			pexpands[key] = self.getvalues(key)
		pos = st.index(0)
		moves = pexpands[pos]
		expstates = []
		for mv in moves:
			nstate = st[:]
			(nstate[pos + mv], nstate[pos]) = (nstate[pos], nstate[pos + 
                    mv])
			expstates.append(nstate)
		return expstates
        
def all_perms(l):
	if len(l) <=1:
		yield l
	else:
		for perm in all_perms(l[1:]):
			for i in range(len(perm)+1):
				yield perm[:i] + l[0:1] + perm[i:]

mapping = {0:0, 1:1, 2:2, 3:5, 4:4, 5:3, 6:6, 7:7, 8:8}

def solvable(l):
	newl = [l[mapping[i]] for i in xrange(9) if l[mapping[i]]!=0]
	#print newl
	return oddreverse(newl)
		
def oddreverse(l):
	#print l
	t = len(l)
	count = 0
	for i in xrange(t):
		for j in xrange(i):
			if l[j]>l[i]:
				count +=1
	if count%2 ==0:
		return False
	return True		
	        
import cPickle

def getfullset():
	if os.path.exists("fullset"):
		f = open('fullset', 'rb')
		return cPickle.load(f)
	else:
		init = [i for i in xrange(9)]
		fullset = [tuple(state) for state in all_perms(init) if solvable(state)]
		print "After generation", len(fullset)
		output = open('fullset', 'wb')
		cPickle.dump(fullset, output)
		return fullset

if (__name__=="__main__"):
	pkl_file = open('ninepuzzle', 'rb')
	d = cPickle.load(pkl_file)
	
	# See how many nodes get extended in A* search, how to??/
	
	
	solved = set([i for i in d.iterkeys()])
	full = set(getfullset())
	flag = True
	counter = 0
	while flag:
		if len(solved) == len(full):
			print "Done"
			output = open('ninepuzzle', 'wb')
			cPickle.dump(d, output)
			print "Dump d", len(d)
			break
			#exit(0)	
		unsolved = full - solved
		state = unsolved.pop()
		print "Going to solve", state
		instance = EightPuzzle(state)
		a = astar_search(instance, instance.h)
		print "Solved"
		
		t = len(a.path())
		for i, j in enumerate(a.path()):
			if tuple(j.state) not in solved:
				counter +=1
				d[j.state] = i
				solved.add(tuple(j.state))
			
		if counter>200:
			counter = 0
			output = open('ninepuzzle', 'wb')
			cPickle.dump(d, output)
			print "Dump d", len(d)
